/**
 * 快速排序：适用于线性表的顺序存储和链式存储
 * 空间复杂度:
 * 		最好空间复杂度：O(n)
 * 		最坏空间复杂度：O(nlogn)
 * 时间复杂度:
 * 		最好的时间复杂度：O(nlogn)
 * 		最坏的时间复杂度：O(n^2)
 * 		平均时间复杂度:接近于O(nlogn)
 * 算法稳定性:不稳定
 * 
 * 快速排序的时间与划分区域是否对称有关，快速排序是所有内部排序中平均性能最优的排序算法;
 * 当初是序列有序或者逆序的时候，快速排序性能最差！
 */

#include <stdio.h>

#define bool int
#define true !0
#define false 0

//快速排序
void QuickSort(int A[], int low, int high);

//用第一个元素A[low]将待排序序列划分成左右两个部分
int Partition(int A[], int low, int high);

int main()
{
	int a[10]={12,43,16,22,63,98,66,90,20,26};
	QuickSort(a,0,9);
	return 0;
}

void QuickSort(int A[], int low, int high)
{
	if(low<high)
	{
		int pivot_pos=Partition(A, low, high);//划分序列，获取到枢纽位置
		QuickSort(A, low, pivot_pos-1);//划分枢纽前左子表
		QuickSort(A, pivot_pos+1, high);//划分枢纽后右字表
	}
}

int Partition(int A[], int low, int high)
{
	int pivot=A[low];		//第一个元素作为枢纽
	while(low < high)		//用low,high表示枢纽的最终位置
	{
		while(low < high && A[high]>=pivot) high--;//A[high]元素大于枢纽元素，high向前移动，寻找比枢纽元素更小的元素
		A[low]=A[high];		//找到比枢纽元素更小的元素A[high]<pivot,则将A[high]放到A[low]处
		while(low < high && A[low]<=pivot) low++; //A[low]元素小于枢纽的元素，low向后移动，直到找到比枢纽更大的元素	
		A[high]=A[low];		//找到比枢纽元素更大的元素A[low]>pvcot,则将A[low]放到A[high]处
	}	
	A[low]=pivot;//一趟遍历完，将枢纽元素放到low处，此时low=high
	return pivot; //返回枢纽的位置
}